﻿using System;

public class RandomAccessQueue<T>
{
    private T[] _buffer;
    private int _head; // 指向队头元素
    private int _tail; // 指向下一个入队位置
    private int _count;

    public RandomAccessQueue(int capacity = 256)
    {
        _buffer = new T[capacity];
        _head = 0;
        _tail = 0;
        _count = 0;
    }

    // 入队
    public void Enqueue(T item)
    {
        if (_count == _buffer.Length)
            Resize(_buffer.Length * 2);

        _buffer[_tail] = item;
        _tail = (_tail + 1) % _buffer.Length; // 循环到数组开头
        _count++;
    }

    // 出队
    public T Dequeue()
    {
        if (_count == 0)
            throw new InvalidOperationException("Queue is empty");

        T item = _buffer[_head];
        _head = (_head + 1) % _buffer.Length; // 循环到数组开头
        _count--;
        return item;
    }

    public T Last()
    {
        return this[this.Count - 1];
    }
    public T First()
    {
        return this[0];
    }
    // 随机访问：索引0对应队头元素
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= _count)
                throw new IndexOutOfRangeException();
            return _buffer[(_head + index) % _buffer.Length];
        }
        set
        {
            if (index < 0 || index >= _count)
                throw new IndexOutOfRangeException();
            _buffer[(_head + index) % _buffer.Length] = value;
        }
    }

    public int Count => _count;

    private void Resize(int newCapacity)
    {
        T[] newBuffer = new T[newCapacity];
        // 分两段复制：从_head到数组末尾 + 从数组开头到_tail
        if (_head < _tail)
        {
            Array.Copy(_buffer, _head, newBuffer, 0, _count);
        }
        else
        {
            Array.Copy(_buffer, _head, newBuffer, 0, _buffer.Length - _head);
            Array.Copy(_buffer, 0, newBuffer, _buffer.Length - _head, _tail);
        }
        _buffer = newBuffer;
        _head = 0;
        _tail = _count;
    }
}